package com.tanzc.sort;

import com.tanzc.util.ArrayUtils;

import java.util.Date;

/**
 * <p> description: 堆排序</p>
 *
 * @author tanzc
 * @date 2021/12/30
 **/
public class HeapSort {
    public static void main(String[] args) {
        HeapSort heapSort = new HeapSort();
        int num = 10000000, max = num * 5;
//        int[] arr = ArrayUtils.random(num, max);
        int[] arr = ArrayUtils.worst(num);
//        int[] arr = ArrayUtils.bad(num);
//        int[] arr = ArrayUtils.nice(num);

        int[] arr1 = new int[num];
        System.arraycopy(arr, 0, arr1, 0, num);
//        ArrayUtils.printArray(arr1);

        System.out.print("堆排序-----time: ");
        Date start = new Date();
        heapSort.heap(arr1);
        Date end = new Date();
        long timediff = end.getTime() - start.getTime();
        System.out.println(timediff + "ms");
//        ArrayUtils.printArray(arr1);
    }

    /**
     * 堆排序
     * 堆，是一种顺序存储的完全二叉树，每个节点都不大于其子节点的堆称为小根堆，反之为大根堆
     * 堆排序就是通过不停构造大根堆/小根堆的方式找出最大/最小值，从而实现对序列排序
     *
     * 构造初始堆时，需要倒序遍历进行多次堆调整，是一系列自底向上的过程
     * 在后续调整无序区有序区时，由于将一个较小元素交换到了堆顶，所以只需从堆顶自上而下进行依次堆调整即可
     *
     *
     * @param arr
     */
    public void heap(int[] arr) {
        // 构建初始大根堆，由于采用顺序存储，根据顺序存储父子节点索引关系，直接从arr.length / 2开始遍历
        // 这里注意是从arr.length / 2 开始的倒序遍历构造堆，这样可以保证初始大根堆的正确性
        for (int i = arr.length / 2; i >= 0; i--) {
            heapAdjust(arr, i, arr.length);
        }
        // 每轮堆调整找出无序区最大元素并移至无序区末尾，无序区长度减一
        // 这样可以不破坏原有的堆结构
        for (int i = arr.length - 1; i > 0; i--) {
            int tmp = arr[i];
            arr[i] = arr[0];
            arr[0] = tmp;

            heapAdjust(arr, 0, i);
        }
    }

    /**
     * 堆调整
     * 指定堆调整起始位置与堆大小
     * @param arr
     * @param parent
     * @param len
     */
    public void heapAdjust(int[] arr, int parent, int len) {
        int tmp = arr[parent];
        // 先选中左孩子节点
        int child = parent * 2 + 1;
        while (child < len) {
            // 如果有右孩子节点，节点选为最大的孩子节点
            if (child + 1 < len && arr[child] < arr[child + 1]) {
                child++;
            }
            // 如果节点比子节点大，则直接跳出循环
            if (tmp >= arr[child]) {
                break;
            }
            // 如果节点比子节点小，则将子节点值提到父节点，并将堆调整位置设置为子节点，循环
            // 这里使用递归进行调整也行，使用循环调整也行
            // 之所以可以这样层层调整得到新的大根堆，而不用担心隔层元素的大根关系，是因为在构造初始堆时，已经构造出了一个大根堆
            arr[parent] = arr[child];
            parent = child;
            child = child * 2 + 1;
        }
        // 堆调整开始位置的值放入最终的堆调整位置
        // 就是因为这个tmp可能较小，所以上面的堆调整才会层层向下，保证将较大的元素往上提
        arr[parent] = tmp;
    }
}
